要處理的資料在同一台電腦裡面，如果資料量超過實際記憶體能夠存取的範圍的話，在存取時就必須要到硬碟裡面把資料撈出來。所以實際上整個程式運作的瓶頸便是在與硬碟溝通所花費的時間。在考量外部存取模型中的演算法時（或把一個演算法應用在該模型時），通常要注意的是極力避免隨機存取，應該要盡量存取儲存位置相近的資料集。

兩種方向

這時候便衍伸出兩種不同的研究方向：（一）改變既有的演算法，讓演算法盡量以循序方式處理資料。（二）改變資料存儲的邏輯與方式，使得演算法存取資料時其位置能夠盡量集中。

第一個會是演算法結構的問題，第二個相較之下就是比較資料結構的問題了。舉例來說，在排序時我們會傾向於使用合併排序法的 bottom-up 實作方式（被稱為外部排序法 External Sort）。為了支援快速搜尋，有效利用一個 page/block 可以存放許多索引的特性，發展出了 B+ Tree 和他們的諸多變化。

參考資料[1]從資料排序、資料搜索與選取、資料置換、幾何問題、線上問題、字串問題下手，分別分析了在這些常見的問題下，如何分析外部存取模型帶來的 cost，大家有興趣可以參考參考～

題外話

好吧，我對外部存取模型沒有太多研究，這東西又被稱為 EM 模型、EM 演算法，光聽就覺得會把 EM 演算法跟 EM 演算法混淆（超級大誤）

參考資料
[1]: https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/models_of_computation/ExternalMemorySurveyVitter.pdf